package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @id: 295
 * @title: 数据流的中位数
 */
 
//中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 
//
// 例如， 
//
// [2,3,4] 的中位数是 3 
//
// [2,3] 的中位数是 (2 + 3) / 2 = 2.5 
//
// 设计一个支持以下两种操作的数据结构： 
//
// 
// void addNum(int num) - 从数据流中添加一个整数到数据结构中。 
// double findMedian() - 返回目前所有元素的中位数。 
// 
//
// 示例： 
//
// addNum(1)
//addNum(2)
//findMedian() -> 1.5
//addNum(3) 
//findMedian() -> 2 
//
// 进阶: 
//
// 
// 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？ 
// 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？ 
// 
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 
// 👍 471 👎 0

public class P295FindMedianFromDataStream {
    public static void main(String[] args) {
        MedianFinder solution = new P295FindMedianFromDataStream().new MedianFinder();
        // todo
        List<Double> result = new ArrayList<>();
        solution.addNum(1);
        solution.addNum(2);
        result.add(solution.findMedian());
        solution.addNum(3);
        result.add(solution.findMedian());
        System.out.println(result);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class MedianFinder {
    private PriorityQueue<Integer> lt;
    private PriorityQueue<Integer> gt;

    /** initialize your data structure here. */
    public MedianFinder() {
        lt = new PriorityQueue<>((a, b) -> (b - a));
        gt = new PriorityQueue<>((a, b) -> (a - b));
    }
    
    public void addNum(int num) {
        if (lt.isEmpty() || num <= lt.peek()) {
            lt.offer(num);
            if (!isOdd()) {
                gt.offer(lt.poll());
            }
        } else {
            gt.offer(num);
            if (isOdd()) {
                lt.offer(gt.poll());
            }
        }
    }
    
    public double findMedian() {
        if (isOdd()) {
            return lt.peek();
        }
        return (lt.peek() + gt.peek()) / 2.0;
    }

    // 是否奇数
    private boolean isOdd() {
        return (lt.size() + gt.size()) % 2 != 0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)


}